from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        tem = []
        candidates.sort()

        def backStack(nextIndex, nextTar):
            if nextTar == 0:
                res.append(tem[:])
                return
            for i in range(nextIndex, len(candidates)):
                if nextTar < candidates[i]:
                    break
                if i > nextIndex and candidates[i] == candidates[i - 1]:
                    continue
                tem.append(candidates[i])
                backStack(i + 1, nextTar - candidates[i])
                tem.pop()

        backStack(0, target)
        return res


if __name__ == "__main__":
    solution = Solution()
    res = solution.combinationSum2(candidates=[10, 1, 2, 7, 6, 1, 5], target=8)
    print(res)
